package com.lh.util.controller;

import com.lh.util.dao.Edge;
import com.lh.util.dao.Node;
import com.lh.util.dao.Vertex;
import com.lh.util.service.vertexService;
import org.springframework.beans.factory.annotation.Autowired;
import org.springframework.web.bind.annotation.RequestBody;
import org.springframework.web.bind.annotation.RequestMapping;
import org.springframework.web.bind.annotation.RestController;

import java.util.Map;
import java.util.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

import static java.lang.Math.min;

@RestController
@RequestMapping("/Vertex")
public class vertexController {

    @Autowired
    private vertexService vertexService;

    @RequestMapping("/listAllVertex")
    public List<Vertex> listAllVertex(){
        return vertexService.listAllVertex();
    }

    @RequestMapping("/newCityInfo")
    public int newCityInfo(@RequestBody Vertex vertex){return vertexService.newCityInfo(vertex);}

    @RequestMapping("/findDistance")
    public int findDistance()
    {
        // 完全图使用prim算法
        List<Vertex> vertexList = vertexService.listAllVertex();

        final int INF = Integer.MAX_VALUE, N = 510;
        final int[][] g = new int[N + 1][N + 1];
        final int[] dist = new int[N + 1];
        final boolean[] st = new boolean[N + 1];

        //System.out.println(vertexList);
        List<Edge> edges = new ArrayList<>();
        System.out.println(vertexList.size());
        getEdges(vertexList, edges);

        for(int i = 0; i < N; i ++)
        {
            for(int j = 0; j < N; j ++ )
            {
                if(i == j) g[i][j] = 0;
                else g[i][j] = INF;
            }
        }
        Arrays.fill(dist, INF);
        Arrays.fill(st, false);
        for (Edge edge : edges)
        {
            int a, b;
            double c;
            // 用ID存储的邻接矩阵
            a = edge.getVertex1().getVertexId();
            b = edge.getVertex2().getVertexId();
            c = edge.getDistance();
            // 使用ID存储邻接矩阵
            g[a][b] = (int)c;
            g[b][a] = (int)c;
        }
        int res = 0;
        for(int i = 0; i < vertexList.size(); i ++ )
        {
            int t = -1;
            // 点的id 从1开始 但vertexList下标从0开始
            for(int j = 0; j < vertexList.size(); j ++ )
            {
                // 第j个ID是否被使用
                if(!st[vertexList.get(j).getVertexId()] &&
                        (t == -1 || dist[vertexList.get(t).getVertexId()] > dist[vertexList.get(j).getVertexId()]))
                {
                    // 把索引给t
                    t = j;
                }

            }

            st[vertexList.get(t).getVertexId()] = true;

            // java中要现将int转为boolean真值的形式 在进行计算
            if (i != 0 && dist[vertexList.get(t).getVertexId()] == INF)
            {
                return INF;
            }
            if (i != 0)
            {
                res += dist[vertexList.get(t).getVertexId()];
            }

            for (Vertex vertex : vertexList) {
                dist[vertex.getVertexId()] =
                        min(dist[vertex.getVertexId()],
                                g[vertexList.get(t).getVertexId()][vertex.getVertexId()]);
            }

        }
        //System.out.println(res);
        return res;
    }


    static int[] f; // f[x]: x的父节点

    // 查找根节点 并 路径压缩
    static int find(int a)
    {
        if(f[a] != a) // 非根节点
        {
            f[a] = find(f[a]);
        }
        return f[a];
    }
    @RequestMapping("/findAllEdges")
    public List<Edge> findAllEdges()
    {
        final int INF = Integer.MAX_VALUE, N = 510;
        // 目标返回List
        List<Edge> edgesList = new ArrayList<>();

        List<Vertex> vertexList = vertexService.listAllVertex();
        List<Edge> edges = new ArrayList<>();
        getEdges(vertexList, edges);
        Node[] nodes = new Node[edges.size()];  // 存储所有边 排序
        for(int i = 0; i < edges.size(); i++) {
            int a = edges.get(i).getVertex1().getVertexId();
            int b = edges.get(i).getVertex2().getVertexId();
            double w1 = edges.get(i).getDistance();
            int w = (int)w1;
            nodes[i] = new Node(a, b, w, i);
        }
        Arrays.sort(nodes);
        f = new int[N];
        for(int i = 0; i < N; i++)
            f[i] = i;
        for(int i = 0; i < edges.size(); i++) {
            int a = nodes[i].a, b = nodes[i].b;
            // 询问a和b是否在一个集合
            if(find(a) != find(b)) {
                edgesList.add(edges.get(nodes[i].i));
                // 不在一个, ab连通, 合并!
                f[find(a)] = find(b);
            }
        }
        return edgesList;
    }

    @RequestMapping("/findDist")
    public int findDist()
    {
        final int INF = Integer.MAX_VALUE, N = 510;
        // 目标返回List
        List<Node> edgesList = new ArrayList<>();

        List<Vertex> vertexList = vertexService.listAllVertex();
        List<Edge> edges = new ArrayList<>();
        getEdges(vertexList, edges);
        Node[] nodes = new Node[edges.size()];  // 存储所有边 排序
        for(int i = 0; i < edges.size(); i++) {
            int a = edges.get(i).getVertex1().getVertexId();
            int b = edges.get(i).getVertex2().getVertexId();
            double w1 = edges.get(i).getDistance();
            int w = (int)w1;
            nodes[i] = new Node(a, b, w, i);
        }
        Arrays.sort(nodes);
        f = new int[N];
        for(int i = 0; i < N; i++) // 并查集要初始化N个 只初始化到vertexList.size()个会ArrayIndexOutOfBoundsException
            f[i] = i;
        int res = 0;
        for(int i = 0; i < edges.size(); i++) {
            int a = nodes[i].a, b = nodes[i].b, w = nodes[i].w;
            // 询问a和b是否在一个集合
            if(find(a) != find(b)) {
                res += w;
                edgesList.add(nodes[i]);
                // 不在一个, ab连通, 合并!
                f[find(a)] = find(b);
            }
        }
        return res;
    }

    private void getEdges(List<Vertex> vertexList, List<Edge> edges) {
        for(int i = 0; i < vertexList.size(); i ++ )
        {
            for(int j = i + 1; j < vertexList.size(); j ++)
            {
                Edge edge = new Edge(vertexList.get(i), vertexList.get(j));
                edges.add(edge);
            }
        }
    }
}
